{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最长公共子串\n",
    "\n",
    "找到两个字符串之间的最长的公共子串，如`hish`与`fish`的最长公共子串为`ish`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-30T03:55:06.574434Z",
     "start_time": "2018-12-30T03:55:06.561684Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('is', 2)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def longestComStr(s1, s2):\n",
    "    # 初始化表格\n",
    "    # 这里因为下面的`row-1`和`col-1`,和背包问题一样需要多出一行和一列\n",
    "    table = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]\n",
    "    # 记录公共自创位置\n",
    "    indexS1 = []\n",
    "    # 填充表格\n",
    "    for row in range(1, len(s1)+1):\n",
    "        for col in range(1, len(s2)+1):\n",
    "            if s1[row-1] == s2[col-1]:\n",
    "                indexS1.append(row-1)\n",
    "                table[row][col] = table[row-1][col-1] + 1\n",
    "    # 找到子串\n",
    "    subStr = ''.join([s1[index] for index in indexS1])\n",
    "    return (subStr, len(indexS1))\n",
    "\n",
    "# test\n",
    "longestComStr('hish', 'vista')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最长公共子序列\n",
    "\n",
    "两个单词中都有的序列包含的字母数，如`fosh`与`fish`包含的最长公共子序列为`f, s, h`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-30T03:54:57.332847Z",
     "start_time": "2018-12-30T03:54:57.319856Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('f,s,h', 3)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def longestComSer(s1, s2):\n",
    "    # 初始化表格\n",
    "    # 这里因为下面的`row-1`和`col-1`,和背包问题一样需要多出一行和一列\n",
    "    table = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]\n",
    "    # 记录公共自创位置\n",
    "    indexS1 = []\n",
    "    # 填充表格\n",
    "    for row in range(1, len(s1)+1):\n",
    "        for col in range(1, len(s2)+1):\n",
    "            if s1[row-1] == s2[col-1]:\n",
    "                indexS1.append(row-1)\n",
    "                table[row][col] = table[row-1][col-1] + 1\n",
    "            else:\n",
    "                table[row][col] = max(table[row-1][col],\n",
    "                                     table[row][col-1])\n",
    "    # 找到子序列\n",
    "    subStr = ','.join([s1[index] for index in indexS1])\n",
    "    return (subStr, len(indexS1))\n",
    "\n",
    "# test\n",
    "longestComSer('fish', 'fosh')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 练习9.3\n",
    "绘制blue和clues的最长公共子串的网格"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-30T12:49:30.097755Z",
     "start_time": "2018-12-30T12:49:30.076498Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 0, 0]\n",
      "[0, 1, 0, 0, 0]\n",
      "[0, 0, 2, 0, 0]\n",
      "[0, 0, 0, 3, 0]\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-2e684896c6a3>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     18\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     19\u001b[0m \u001b[0;31m# test\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 20\u001b[0;31m \u001b[0mlongestComStr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'blue'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'clues'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-6-2e684896c6a3>\u001b[0m in \u001b[0;36mlongestComStr\u001b[0;34m(s1, s2)\u001b[0m\n\u001b[1;32m     12\u001b[0m                 \u001b[0mtable\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mrow\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcol\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtable\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mrow\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcol\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mrow\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtable\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mrow\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m     \u001b[0;31m# 找到子串\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m     \u001b[0msubStr\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m''\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0ms1\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mindex\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mindex\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mindexS1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "def longestComStr(s1, s2):\n",
    "    # 初始化表格\n",
    "    # 这里因为下面的`row-1`和`col-1`,和背包问题一样需要多出一行和一列\n",
    "    table = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]\n",
    "    # 记录公共自创位置\n",
    "    indexS1 = []\n",
    "    # 填充表格\n",
    "    for row in range(1, len(s1)+1):\n",
    "        for col in range(1, len(s2)+1):\n",
    "            if s1[row-1] == s2[col-1]:\n",
    "                indexS1.append(row-1)\n",
    "                table[row][col] = table[row-1][col-1] + 1\n",
    "    # 打印网格\n",
    "    for row in range(1, len(table[:][0])):\n",
    "        print(table[row][1:])\n",
    "    # 找到子串\n",
    "    subStr = ''.join([s1[index] for index in indexS1])\n",
    "    return (subStr, len(indexS1))\n",
    "\n",
    "# test\n",
    "longestComStr('blue', 'clues')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
